package com.algrithom.graph.bfs;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 301. 删除无效的括号
 */
public class Solution5 {
    
    private final Set<String> set = new HashSet<>();
    
    public static void main(String[] args){
        String str = ")(";
        Solution5 solution5 = new Solution5();
        System.out.println(solution5.removeInvalidParentheses(str));
    }
    
    public List<String> removeInvalidParentheses(String s){
        char[] ss = s.toCharArray();
        int open = 0, close = 0;
        // 获取应该去除的左右括号数
        for (char c : ss) {
            if (c == '(') {
                open++;
            } else if (c == ')') {
                if (open > 0) {
                    open--;
                } else {
                    close++;
                }
            }
        }
        // 回溯
        backTracking(ss,new StringBuilder(),0,0,0,open,close);
        return new ArrayList<>(set);
    }
    
    public void backTracking(char[] ss,StringBuilder sb,int index,int open,int close,int openRem,int closeRem){
        // 所有字符都处理完毕
        if (index == ss.length) {
            // 如果应去除的左右括号数都变为0，则将sb插入set
            if (openRem == 0 && closeRem == 0) {
                set.add(sb.toString());
            }
            return;
        }
        // 去掉当前位置的字符（括号），并处理下一个字符
        if (ss[index] == '(' && openRem > 0 || ss[index] == ')' && closeRem > 0) {
            backTracking(ss,sb,index + 1,open,close,openRem - (ss[index] == '(' ? 1 : 0),closeRem - (ss[index] == ')' ? 1 : 0));
        }
        // 不去掉当前位置字符
        // 将当前位置字符插入sb
        sb.append(ss[index]);
        // 当前位置不为括号，则直接处理下一个字符
        if (ss[index] != '(' && ss[index] != ')') {
            backTracking(ss,sb,index + 1,open,close,openRem,closeRem);
        }
        // 当前位置为左括号，增加左括号计数，处理下一个字符
        else if (ss[index] == '(') {
            backTracking(ss,sb,index + 1,open + 1,close,openRem,closeRem);
        }
        // 当前位置为右括号，且当前左括号计数大于右括号计数，则增加右括号计数，处理下一个字符
        else if (open > close) {
            backTracking(ss,sb,index + 1,open,close + 1,openRem,closeRem);
        }
        // 去除当前加入sb的字符
        sb.deleteCharAt(sb.length() - 1);
    }
}
